{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reduce Array Size to The Half"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSetSize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组大小减半"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>arr</code>。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。</p>\n",
    "\n",
    "<p>返回&nbsp;<strong>至少</strong>&nbsp;能删除数组中的一半整数的整数集合的最小大小。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [3,3,3,3,5,5,5,2,2,7]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。\n",
    "大小为 2 的可行集合有 {3,5},{3,2},{5,2}。\n",
    "选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [7,7,7,7,7,7]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>我们只能选择集合 {7}，结果数组为空。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>arr.length</code>&nbsp;为偶数</li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reduce-array-size-to-the-half](https://leetcode.cn/problems/reduce-array-size-to-the-half/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reduce-array-size-to-the-half](https://leetcode.cn/problems/reduce-array-size-to-the-half/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,3,3,3,5,5,5,2,2,7]', '[7,7,7,7,7,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        freq = {}\n",
    "        for num in arr:\n",
    "            if num in freq:\n",
    "                freq[num] += 1\n",
    "            else:\n",
    "                freq[num] = 1\n",
    "\n",
    "        sorted_freq = sorted(freq.values(), reverse=True)\n",
    "        # reverse = True 降序 ， reverse = False 升序（默认)\n",
    "        print(sorted_freq)\n",
    "\n",
    "        target = len(arr) // 2\n",
    "        count = 0\n",
    "        for num_count in sorted_freq:\n",
    "            target -= num_count\n",
    "            count += 1\n",
    "            if target <= 0:\n",
    "                return count\n",
    "        return len(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        # 使用哈希表记录每个数字的出现次数\n",
    "        count_map = {}\n",
    "        for num in arr:\n",
    "            count_map[num] = count_map.get(num, 0) + 1\n",
    "        \n",
    "        # 按照出现次数降序排序\n",
    "        sorted_counts = sorted(count_map.values(), reverse=True)\n",
    "        \n",
    "        # 找到出现次数最多的数字\n",
    "        target_length = len(arr) // 2\n",
    "        current_length = 0\n",
    "        set_size = 0\n",
    "        for count in sorted_counts:\n",
    "            current_length += count\n",
    "            set_size += 1\n",
    "            if current_length >= target_length:\n",
    "                break\n",
    "        \n",
    "        return set_size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        cnt = dict()\n",
    "        for num in arr:\n",
    "            if num not in cnt:\n",
    "                cnt.update({num: 1})\n",
    "            else:\n",
    "                cnt[num] += 1\n",
    "        sorted_index = sorted(cnt.values())[::-1]\n",
    "        acc = 0\n",
    "        size = 0\n",
    "        for cur in sorted_index:\n",
    "            acc += cur\n",
    "            size += 1\n",
    "            if acc >= len(arr) // 2:\n",
    "                return size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        count=len(arr)//2\n",
    "        mydic=collections.Counter(arr)\n",
    "        temp=[]\n",
    "        for i in mydic.values():\n",
    "            temp.append(i)\n",
    "        temp=sorted(temp,reverse=True)\n",
    "        ans=0\n",
    "        sum=0\n",
    "        for i in range(0,len(temp)):\n",
    "            ans=ans+1\n",
    "            sum=sum+temp[i]\n",
    "            if sum>=count:\n",
    "                return ans\n",
    "\n",
    "\n",
    "\n",
    "       \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        cnt = Counter(arr)\n",
    "        n = len(arr)\n",
    "        res = 0\n",
    "        total = 0\n",
    "        rec = [v for k,v in cnt.items()]\n",
    "        rec.sort(reverse=True)\n",
    "        for v in rec:\n",
    "            total += v\n",
    "            res += 1\n",
    "            if total>=n/2:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        half_n = n / 2\n",
    "        n_dict = {}\n",
    "        n_list = []\n",
    "        for n in arr:\n",
    "            if n in n_dict:\n",
    "                n_dict[n] += 1\n",
    "            else:\n",
    "                n_dict[n] = 1\n",
    "        for k,v in n_dict.items():\n",
    "            n_list.append(v)\n",
    "        n_list.sort(reverse=True)\n",
    "        \n",
    "        \n",
    "        print(half_n,'half')\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while half_n > 0:\n",
    "            ans += 1\n",
    "            half_n -= n_list[i]\n",
    "            print(half_n)\n",
    "            i += 1\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        numcount = collections.Counter(arr)\n",
    "        vals = list(numcount.values())\n",
    "        vals.sort()\n",
    "        ans, sumcount= 0, 0\n",
    "        legnth = len(arr)\n",
    "        for val in vals[::-1]:\n",
    "            sumcount += val\n",
    "            ans += 1\n",
    "            if sumcount >= (legnth + 1)//2:\n",
    "                return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        l = len(arr)\n",
    "        num = [0]*100001\n",
    "        stk = []\n",
    "        for i in arr:\n",
    "            num[i]+=1\n",
    "        for i in range(100001):\n",
    "            if(num[i] !=0):\n",
    "                stk.append([i,num[i]])\n",
    "        stk = sorted(stk,key =lambda x:x[1],reverse = True)\n",
    "        s = 0\n",
    "        for i in range(len(stk)):\n",
    "            s+=stk[i][1]\n",
    "            if(s>=l//2):\n",
    "                return i+1\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        book=dict()\n",
    "        for i in arr:\n",
    "            if i in book:\n",
    "                book[i]+=1\n",
    "            else:\n",
    "                book[i]=1\n",
    "        book=list(book.items())\n",
    "        book.sort(key=lambda x:x[1],reverse=True)\n",
    "        res=0\n",
    "        # print(n)\n",
    "        # print(book)\n",
    "        for i in range(len(book)):\n",
    "            res+=book[i][1]\n",
    "            if res>=n//2:return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        N = len(arr)\n",
    "        buckets = collections.defaultdict(int)\n",
    "        for n,c in collections.Counter(arr).items():\n",
    "            buckets[c] += 1\n",
    "        res = 0\n",
    "        left = N/2\n",
    "        for c in reversed(range(N+1)):\n",
    "            if buckets[c] == 0: continue\n",
    "            has = buckets[c]\n",
    "            needs = math.ceil(left/c)\n",
    "            if needs <= has:\n",
    "                res += needs\n",
    "                return res\n",
    "            else:\n",
    "                res += has\n",
    "                left -= c*has\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = len(arr) // 2\n",
    "        counter = Counter(arr)\n",
    "        nums = list(accumulate(sorted(counter.values())))\n",
    "        print(nums)\n",
    "        return len(counter) - bisect.bisect(nums, left)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = len(arr) // 2\n",
    "        counter = Counter(arr)\n",
    "        nums = list(accumulate(sorted(counter.values())))\n",
    "        return len(counter) - bisect.bisect(nums, left)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        num_dict={}\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] not in num_dict:\n",
    "                num_dict[arr[i]]=0\n",
    "            num_dict[arr[i]]+=1\n",
    "        times_list=sorted(num_dict.values(),reverse=True)\n",
    "        if times_list[0]>=(len(arr)//2):\n",
    "            return 1\n",
    "        else:\n",
    "            for i in range(1,len(times_list)):\n",
    "                times_list[i]+=times_list[i-1]\n",
    "                if times_list[i]>=(len(arr)//2):\n",
    "                    return i+1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        hashmap = {}\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] in hashmap:\n",
    "                hashmap[arr[i]] += 1\n",
    "            else:\n",
    "                hashmap[arr[i]] = 1\n",
    "        l = list(set(arr))\n",
    "        ans = []\n",
    "        for j in range(len(l)):\n",
    "            ans.append(hashmap[l[j]])\n",
    "        ans = sorted(ans,reverse=True)\n",
    "        tmp = 0\n",
    "        k = 0\n",
    "        while k < len(ans):\n",
    "            tmp += ans[k]\n",
    "            if tmp >= n/2:\n",
    "                return k+1\n",
    "            k+=1\n",
    "\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        count = Counter(arr)\n",
    "        allNums = list(set(arr))\n",
    "\n",
    "        allNums.sort(key = lambda a: count[a])\n",
    "\n",
    "        res = 0\n",
    "        while n > len(arr) // 2:\n",
    "            n -= count[allNums.pop()]\n",
    "            res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        return bisect_left(list(accumulate(sorted(Counter(arr).values(), reverse=True))), len(arr) // 2) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        length = len(arr)\n",
    "        count = collections.Counter(arr)\n",
    "        Lst = []\n",
    "        for val, num in count.items():\n",
    "            Lst.append([num,val])\n",
    "        Lst.sort(reverse = True)\n",
    "        #print(Lst)\n",
    "        count = 0\n",
    "        length2 = length / 2\n",
    "        for i in range(len(Lst)):\n",
    "            count += Lst[i][0]\n",
    "            if count >= length2:\n",
    "                 return i + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        import collections\n",
    "        d = dict(collections.Counter(arr))\n",
    "        c = sorted(list(d.values()), reverse=True)\n",
    "        l = len(arr)\n",
    "        curl = l\n",
    "        i = 0\n",
    "        while curl > l // 2:\n",
    "            curl -= c[i]\n",
    "            i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    统计每个字符出现的次数\n",
    "    从最大开始删，直到剩余的元素的数量小于等于总长度的一半\n",
    "    时间复杂度：O(nlogn)\n",
    "    空间复杂度：O(n)\n",
    "\n",
    "    \"\"\"\n",
    "    \n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        length = len(arr)\n",
    "        counter = Counter(arr)\n",
    "        tuples = [(k, v) for k, v in counter.items()]\n",
    "        tuples.sort(key=lambda x: x[1], reverse=True)\n",
    "        count = 0\n",
    "        half_len = math.ceil(length // 2)\n",
    "        deleted = 0\n",
    "        for k, v in tuples:\n",
    "            deleted += v\n",
    "            count += 1\n",
    "            if deleted >= half_len:\n",
    "                return count\n",
    "        return length\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        map_cnt = Counter(arr)\n",
    "        map_list = [(key, val) for key, val in map_cnt.items()]\n",
    "        map_list = sorted(map_list, key = lambda x :-x[1])\n",
    "        q = []\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        for key, val in map_list:\n",
    "            cnt += val\n",
    "            ans += 1\n",
    "            if cnt * 2 >= n:\n",
    "                break \n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        hash_ = Counter(arr)\n",
    "        ans = [(-val,key) for key,val in hash_.items()]\n",
    "        n = len(arr)\n",
    "        heapq.heapify(ans)\n",
    "        res = 0\n",
    "        step = 0\n",
    "        while res < n//2 and ans:\n",
    "            step+=1\n",
    "            res -= heapq.heappop(ans)[0]\n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        total = len(arr)\n",
    "        target = total // 2\n",
    "        counter = collections.Counter(arr)\n",
    "        pq = [(-counter[num], num) for num in counter]\n",
    "        heapq.heapify(pq)\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        while cur < target and pq:\n",
    "            time, _ = heapq.heappop(pq)\n",
    "            cur -= time\n",
    "            ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        # max heap \n",
    "        cnt = Counter(arr)\n",
    "        cnt_lst = [(-freq,val) for val,freq in cnt.items()]\n",
    "        heapq.heapify(cnt_lst)\n",
    "\n",
    "        k = len(arr)//2 \n",
    "        res = 0 \n",
    "        while k>0: \n",
    "            freq, val = heapq.heappop(cnt_lst)\n",
    "            k += freq\n",
    "            res += 1 \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        total = len(arr)\n",
    "        target = total // 2\n",
    "        counter = collections.Counter(arr)\n",
    "        pq = [(-counter[num], num) for num in counter]\n",
    "        heapq.heapify(pq)\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        while cur < target and pq:\n",
    "            time, _ = heapq.heappop(pq)\n",
    "            cur -= time\n",
    "            ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        s=Counter(arr)\n",
    "        high_tuple=s.most_common(len(s))\n",
    "        sum_all=0\n",
    "        number=0\n",
    "        print(high_tuple)\n",
    "        while number<len(s):\n",
    "            sum_all+=high_tuple[number][1]\n",
    "            number+=1\n",
    "            if sum_all>=(len(arr)+1)//2:\n",
    "                break\n",
    "        return number\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        freq = collections.Counter(arr)\n",
    "        c, a = 0, 0\n",
    "        for num, occ in freq.most_common():\n",
    "            c += occ\n",
    "            a += 1\n",
    "            if c * 2 >= len(arr):\n",
    "                break\n",
    "        return a\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        for i in arr:\n",
    "            if i in d:\n",
    "                d[i] +=1\n",
    "            else:\n",
    "                d[i] = 1\n",
    "        new_arr = list(set(arr))\n",
    "        new_arr.sort(key=lambda x:d[x],reverse=True)\n",
    "        min_chose = 0\n",
    "        n = len(arr)//2\n",
    "        for i in new_arr:\n",
    "            min_chose +=1\n",
    "            n -= d[i]\n",
    "            if n <= 0 :\n",
    "                break\n",
    "        return min_chose"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        arr_set = set(arr)\n",
    "        arr_dict = dict()\n",
    "        for key in arr_set:\n",
    "            arr_dict[key] = 0\n",
    "        for num in arr:\n",
    "            arr_dict[num] += 1\n",
    "        arr1 = sorted(arr_dict,key=lambda k : arr_dict[k],reverse=True)\n",
    "        ans = 0\n",
    "        n = (len(arr) + 1) // 2\n",
    "        # print(arr1)\n",
    "        # print(arr_dict[arr1[0]])\n",
    "        for v in arr1:\n",
    "            ans += 1\n",
    "            n -= arr_dict[v]\n",
    "            # print(n)\n",
    "            if n <= 0:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        numdict = defaultdict(int)\n",
    "        for num in arr:\n",
    "            numdict[num] += 1\n",
    "        n = len(arr)\n",
    "        numlist = [(numdict[key], key) for key in numdict]\n",
    "        numlist = sorted(numlist, reverse=True)\n",
    "        tot = 0\n",
    "        if n % 2 == 1:\n",
    "            n = n // 2 + 1\n",
    "        else:\n",
    "            n = n // 2\n",
    "        idx = 0\n",
    "        while tot < n:\n",
    "            tot += numlist[idx][0]\n",
    "            idx += 1\n",
    "        return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        counter = {}\n",
    "        for c in arr:\n",
    "            if c not in counter.keys():\n",
    "                counter[c] = 1\n",
    "            else:\n",
    "                counter[c] = counter[c] + 1\n",
    "        counter = sorted(counter.items(),key = lambda x:x[1],reverse = True)\n",
    "        print(counter)\n",
    "        sum = 0\n",
    "        result = 0\n",
    "        for x in counter:\n",
    "            v = x[1]\n",
    "            if v + sum >= math.ceil(len(arr)/2):\n",
    "                return result + 1\n",
    "            else:\n",
    "                sum = v + sum\n",
    "                result = result + 1\n",
    "\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        d=Counter(arr)\n",
    "        h=[]\n",
    "        for k,v in d.items():\n",
    "            heappush(h,[-v,k])\n",
    "        s=0\n",
    "        n=len(arr)\n",
    "        t=(n+1)//2\n",
    "        while n>t:\n",
    "            x=heappop(h)\n",
    "            s+=1\n",
    "            n+=x[0]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        arr_l = list(set(arr))\n",
    "        temp = [0]*len(arr_l)\n",
    "        dict_1 = dict(zip(arr_l,temp))\n",
    "        for _ in range(len(arr)):\n",
    "            dict_1[arr[_]]+=1\n",
    "        temp2 = []\n",
    "        for k,v in dict_1.items():\n",
    "            temp2.append((k,v))\n",
    "        temp2.sort(key=lambda x:-x[1])\n",
    "        #print(temp2)\n",
    "        temp3 = []\n",
    "        for _ in range(len(temp2)):\n",
    "            temp3.append(temp2[_][1])\n",
    "        length = len(arr)//2\n",
    "        count = 0\n",
    "        count2 = 0\n",
    "        for _ in range(len(temp3)):\n",
    "            count2+=temp3[_]\n",
    "            count+=1\n",
    "            if count2>=length:\n",
    "                break\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        d = dict(Counter(arr))\n",
    "        freq = sorted(d.values(), reverse=True)\n",
    "        n = len(arr)\n",
    "        target = n // 2\n",
    "        count = 0\n",
    "        removed = 0\n",
    "\n",
    "        for f in freq:\n",
    "            count += 1\n",
    "            removed += f\n",
    "            if removed >= target:\n",
    "                break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        m = Counter(arr)\n",
    "        p = sorted([(m[k], k) for k in m], key=lambda x:-x[0])\n",
    "        \n",
    "        s = cnt = 0\n",
    "        for v, k in p:\n",
    "            cnt += 1\n",
    "            s += v\n",
    "            if s >= n//2:\n",
    "                return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        dic=dict(Counter(arr))\n",
    "        l=list(dic.values())\n",
    "        l.sort(reverse=True)\n",
    "        length=len(arr)//2\n",
    "        total=0\n",
    "        for i in range(len(l)):\n",
    "            total+=l[i]\n",
    "            if total>=length:\n",
    "                return i+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        res=0\n",
    "        v=0\n",
    "        freq = collections.Counter(arr)\n",
    "        for i,j  in freq.most_common():\n",
    "            res+=1\n",
    "            v+=j\n",
    "            if v>=len(arr)//2:\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        hal_len = n // 2\n",
    "        count_arr = Counter(arr)\n",
    "        list_count = sorted(list(count_arr.items()), key=lambda x: x[1], reverse=True)\n",
    "        cc, ans = 0, 0\n",
    "        for x, y in list_count:\n",
    "            cc += y\n",
    "            ans += 1\n",
    "            if cc >= hal_len:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        count = Counter(arr)\n",
    "        num,ans = 0,0\n",
    "        for k,v in count.most_common():\n",
    "            num += v\n",
    "            ans += 1\n",
    "            if num >= n//2:\n",
    "                return ans\n",
    "        '''\n",
    "        arr2 = []\n",
    "        for k,v in count.items():\n",
    "            arr2.append([k,v])\n",
    "        arr2.sort(key=lambda x: -x[1])\n",
    "        num = 0\n",
    "        for k,v in arr2:\n",
    "            num += v\n",
    "            ans += 1\n",
    "            if num >= n//2:\n",
    "                return ans\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        freq = Counter(arr)\n",
    "        freq = sorted(freq.items(), key=lambda x:x[1],reverse=True)\n",
    "        cnt, ans = 0, 0\n",
    "        for num, occ in freq:\n",
    "            cnt += occ\n",
    "            ans += 1\n",
    "            if cnt * 2 >= len(arr):\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        count = Counter(arr)\n",
    "        # 按照次数降序排列\n",
    "        count = sorted(count.items(),key=lambda x:x[1],reverse=True)\n",
    "        res,ans = 0,0\n",
    "        for i in count:\n",
    "            if i[1] >= n/2:\n",
    "                return 1\n",
    "            else:\n",
    "                res += i[1]\n",
    "                ans += 1\n",
    "                if res >= n/2:\n",
    "                    return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        dic = Counter(arr)\n",
    "        dic = sorted(dic.items(), key = lambda x:x[1], reverse = True)\n",
    "        n = len(arr) / 2\n",
    "        cnt = 0\n",
    "        res = []\n",
    "        for k, value in dic:\n",
    "            cnt += value\n",
    "            res.append(k)\n",
    "            if cnt >= n:\n",
    "                break\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        ref = {}\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            if arr[i] in ref:\n",
    "                ref[arr[i]] += 1\n",
    "            else:\n",
    "                ref[arr[i]] = 1\n",
    "        book = [(key, ref[key]) for key in ref.keys()]\n",
    "        book.sort(key=lambda x:x[1], reverse = True)\n",
    "        res = 0\n",
    "        tmp = 0\n",
    "        for i in range(len(book)):\n",
    "            tmp += book[i][1] \n",
    "            res += 1\n",
    "            if tmp >= n // 2:\n",
    "                return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        count = Counter(arr)\n",
    "        count = list(count.items())\n",
    "        count.sort(key = lambda x: x[1], reverse=True)\n",
    "        count = [x[1] for x in count]\n",
    "        import bisect\n",
    "        from itertools import accumulate\n",
    "        preSum = list(accumulate(count))\n",
    "        index = bisect.bisect_left(preSum, len(arr)//2)\n",
    "\n",
    "        return index+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        counter = Counter(arr)\n",
    "        items = list(counter.items())\n",
    "        items.sort(key=lambda x: x[1], reverse=True)\n",
    "        half = len(arr)//2 if len(arr)%2 == 0 else len(arr)//2+1\n",
    "        print(items, half)\n",
    "        result = 0\n",
    "        sums = 0\n",
    "        for _, cnt in items:\n",
    "            result += 1\n",
    "            sums += cnt\n",
    "            if sums >= half:\n",
    "                return result\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        total=len(arr)\n",
    "        count=Counter(arr)\n",
    "        countlist=[]\n",
    "        for k,v in count.items():\n",
    "            countlist.append([k,v])\n",
    "        countlist.sort(key=lambda x:-x[1])\n",
    "        k=0\n",
    "        n=len(countlist)\n",
    "        for i in range(n):\n",
    "            if k>=total/2:\n",
    "                return i\n",
    "            k+=countlist[i][1]\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        arr_len = len(arr)\n",
    "        arr1 = collections.Counter(arr)\n",
    "        arr2 = list(arr1.items())\n",
    "\n",
    "        for pos, item in enumerate(arr2):\n",
    "            arr2[pos] = [item[1], item[0]]\n",
    "        arr2 = sorted(arr2, reverse=True)\n",
    "\n",
    "        for pos, item in enumerate(arr2):\n",
    "            if pos == 0:\n",
    "                arr2_sum = [item[0]]\n",
    "            else:\n",
    "                arr2_sum.append(arr2_sum[pos - 1] + item[0])\n",
    "\n",
    "            if arr2_sum[pos] >= arr_len / 2:\n",
    "                return pos + 1\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr):\n",
    "        n = len(arr)\n",
    "        n = (n + 1) // 2\n",
    "        index={i:0 for i in set(arr)}\n",
    "        for i in arr:\n",
    "            index[i]+=1\n",
    "        index=[i for i in index.items()]\n",
    "        index.sort(key=lambda x: x[1], reverse=True)\n",
    "        a = 0\n",
    "        ans = 0\n",
    "        for i in range(len(index)):\n",
    "            if a >= n:\n",
    "                return ans\n",
    "            a += index[i][1]\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        d_arr = dict(Counter(arr))\n",
    "        if len(d_arr) == 1:\n",
    "            return 1\n",
    "        else:            \n",
    "            d_arr = sorted(d_arr.items(),key=lambda x:x[1],reverse=True)\n",
    "            min_count = 0\n",
    "            nums_count = 0    \n",
    "            for k, v in d_arr:\n",
    "                min_count += 1\n",
    "                nums_count += v\n",
    "                if nums_count >= n/2:\n",
    "                    break\n",
    "            return min_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        count = Counter(arr)\n",
    "        arr2 = []\n",
    "        for k,v in count.items():\n",
    "            arr2.append([k,v])\n",
    "        arr2.sort(key=lambda x: -x[1])\n",
    "        num = 0\n",
    "        for k,v in arr2:\n",
    "            num += v\n",
    "            ans += 1\n",
    "            if num >= n//2:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            dic[arr[i]] = dic.get(arr[i],0) + 1\n",
    "        heap = []\n",
    "        for key, val in dic.items():\n",
    "            heapq.heappush(heap, [-val, key])\n",
    "        cnt = 0\n",
    "        new_n = n\n",
    "        while heap and new_n > n/2:\n",
    "            e = heapq.heappop(heap)\n",
    "            new_n = new_n + e[0]\n",
    "            cnt += 1\n",
    "        return cnt\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "首先获得数组长度 n = len(arr)\n",
    "\n",
    "然后使用一个字典保存每个数字的出现次数和数字本身[出现次数：数字本身]，比如排序，排序可以用sorted，不过这里使用大根堆\n",
    "\n",
    "弹出的元素 e[0]，如果n-e[0]小于等于n/2，那么return res\n",
    "\n",
    "如果还不到，则继续pop，每次将e[1]添加res中，并更新n的大小\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        counter=Counter(arr)\n",
    "        left=0\n",
    "        right=len(counter)\n",
    "        n=len(arr)\n",
    "        def isvliad(num_set):\n",
    "            #print(counter.most_common(num_set))\n",
    "            local_=sum(x[1] for x in counter.most_common(num_set)) \n",
    "            return local_>=n//2\n",
    "        \n",
    "\n",
    "        while(left<right):\n",
    "            mid=int(left+(right-left)/2)\n",
    "\n",
    "            if(isvliad(mid)):\n",
    "                right=mid \n",
    "            else:\n",
    "                left=mid+1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = collections.defaultdict(int)\n",
    "        cur, res = 0, 1\n",
    "        for i in range(n):\n",
    "            ans[arr[i]] += 1\n",
    "        ans = dict(sorted(ans.items(), key=lambda k: k[1], reverse=True))\n",
    "        for num in ans:\n",
    "            if cur + ans[num] < n // 2:\n",
    "                cur += ans[num]\n",
    "                res += 1\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        num_cnt_dict,length,res={},len(arr),0\n",
    "        for n in arr:\n",
    "            if n not in num_cnt_dict:\n",
    "                num_cnt_dict[n]=1\n",
    "            else:\n",
    "                num_cnt_dict[n]+=1\n",
    "        \n",
    "        num_cnt_dict,newlen={k:v for k,v in sorted(num_cnt_dict.items(),key=lambda x:x[1],reverse=True)},0\n",
    "        for k in num_cnt_dict:\n",
    "            newlen+=num_cnt_dict[k]\n",
    "            res+=1\n",
    "            if newlen*2>=length:\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr):\n",
    "        n = len(arr)\n",
    "        n = (n + 1) // 2\n",
    "        ar = list(set(arr))\n",
    "        ii = {k: i for i, k in enumerate((ar))}\n",
    "        index = [[i, 0] for i in ar]\n",
    "        for i in arr:\n",
    "            j = ii[i]\n",
    "            index[j][1] += 1\n",
    "\n",
    "        index.sort(key=lambda x: x[1], reverse=True)\n",
    "        a = 0\n",
    "        ans = 0\n",
    "        for i in range(len(index)):\n",
    "            if a >= n:\n",
    "                return ans\n",
    "            a += index[i][1]\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) :\n",
    "        d={}\n",
    "        length = len(arr)\n",
    "        for i in arr:\n",
    "            if(not (i in d.keys())):\n",
    "                d[i] = 1\n",
    "            else:\n",
    "                d[i] += 1\n",
    "        cnt = 0;\n",
    "        now = 0\n",
    "        d=dict(sorted(d.items(), key=lambda x: x[-1], reverse=True))\n",
    "       \n",
    "        for key in d.keys():\n",
    "            cnt += 1\n",
    "            now += d[key]\n",
    "            if(length - now <= length/2):\n",
    "                return cnt\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "\n",
    "        c = Counter(arr)\n",
    "        count = 0\n",
    "        ans = 0\n",
    "        for k,v in Counter(arr).most_common():\n",
    "            count += v\n",
    "            ans += 1\n",
    "            if count>= len(arr)/2:\n",
    "                return ans\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        counter_dict = dict(Counter(arr))\n",
    "        print(counter_dict)\n",
    "        deleted_count = 0\n",
    "        res = []\n",
    "        for tup in sorted(counter_dict.items(), key=lambda x: x[1], reverse=True):\n",
    "            key, val = tup\n",
    "            deleted_count += val\n",
    "            res.append(key)\n",
    "            if deleted_count >= len(arr) // 2:\n",
    "                break\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        counter_dict = dict(Counter(arr))\n",
    "        print(counter_dict)\n",
    "        deleted_count = 0\n",
    "        res = []\n",
    "        for tup in sorted(counter_dict.items(), key=lambda x: x[1], reverse=True):\n",
    "            key, val = tup\n",
    "            deleted_count += val\n",
    "            res.append(key)\n",
    "            if deleted_count >= len(arr) // 2:\n",
    "                break\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        c = Counter(arr)\n",
    "        leng = len(arr)\n",
    "        z_leng = 0\n",
    "        s_leng = 0\n",
    "        s0_leng = len(c)\n",
    "        half_leng = 1/2*leng\n",
    "        z = dict(sorted(c.items(), key=lambda item: item[1]))\n",
    "        for items in z:\n",
    "            z_leng = z_leng + z[items]\n",
    "            s_leng = s_leng + 1\n",
    "            if z_leng > half_leng:\n",
    "                return s0_leng - s_leng + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        l = len(arr)\n",
    "        dist = Counter(arr)\n",
    "        dist1 = sorted(dist.items(), key = lambda kv: (kv[1], kv[0]), reverse = True)\n",
    "        sum, res = 0, 0\n",
    "        for i,j in dist1:\n",
    "            sum += j\n",
    "            res += 1\n",
    "            if 2*sum >= l:\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        length=len(arr)\n",
    "        tmp={}\n",
    "        for i in range(length):\n",
    "            sting=str(arr[i])\n",
    "            if sting in tmp:\n",
    "                tmp[sting] +=1\n",
    "            else:\n",
    "                tmp[sting] = 1\n",
    "        tmp2=sorted(tmp.items(), key=lambda x: x[1], reverse=True)\n",
    "        ll=len(tmp2)\n",
    "        count = 0\n",
    "        i_count = 0\n",
    "        for j in range(ll):\n",
    "            count += tmp2[j][1]\n",
    "            i_count += 1\n",
    "            if count >= 0.5*length:\n",
    "                return i_count\n",
    "        return null\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "\n",
    "        counter = {}\n",
    "        for num in arr:\n",
    "            if num not in counter:\n",
    "                counter[num] = 1\n",
    "            else:\n",
    "                counter[num] += 1\n",
    "        \n",
    "        queue = []\n",
    "        for num, times in list(counter.items()):\n",
    "            queue.append((-times, num))\n",
    "        \n",
    "        heapq.heapify(queue)\n",
    "        res = 0\n",
    "        count = 0\n",
    "        target = len(arr) // 2 if len(arr) % 2 == 0 else len(arr) // 2 + 1\n",
    "        while res < target:\n",
    "            res += -heapq.heappop(queue)[0]\n",
    "            count += 1\n",
    "\n",
    "        return count\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        c = Counter(arr)\n",
    "        l = []\n",
    "        visited = set()\n",
    "        for val in arr:\n",
    "            if val not in visited:\n",
    "                l.append((c[val], val))\n",
    "                visited.add(val)\n",
    "        l.sort(key = lambda x:-x[0])\n",
    "\n",
    "        res, reduced_size = 0, 0\n",
    "        for freq, val in l:\n",
    "            reduced_size += freq\n",
    "            res += 1\n",
    "            if reduced_size >= len(arr) // 2:\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        cnt = collections.defaultdict(int)\n",
    "        for a in arr:\n",
    "            cnt[a] += 1\n",
    "        ls = []\n",
    "        for i in cnt.keys():\n",
    "            ls.append(cnt[i])\n",
    "        ls = sorted(ls, reverse=True)\n",
    "        ma = len(arr) // 2\n",
    "        tj = 0\n",
    "        ans = 0\n",
    "        for i in ls:\n",
    "            tj += i\n",
    "            ans += 1\n",
    "            if tj >= ma:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        index_dir = {}\n",
    "        arr_set = set(arr)\n",
    "\n",
    "        for i in arr_set:\n",
    "            index_dir[i] = 0\n",
    "\n",
    "        for i in arr:\n",
    "            index_dir[i] = index_dir[i]+1\n",
    "\n",
    "        print(index_dir)\n",
    "\n",
    "        index_dir_order = dict(sorted(index_dir.items(),key=lambda x:x[1],reverse= True))\n",
    "        print(index_dir_order)\n",
    "        count = 0\n",
    "        result = 0\n",
    "        for v in index_dir_order.values():\n",
    "            result += 1\n",
    "            count += v\n",
    "            if count >= len(arr)/2:\n",
    "                return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        arr_len = len(arr)\n",
    "        counted = dict(collections.Counter(arr))\n",
    "        sort_counted = {k:v for k,v in sorted(counted.items(), key=lambda item:item[1], reverse=True)}\n",
    "        res = 0\n",
    "        total = 0\n",
    "        for k,v in sort_counted.items():\n",
    "            if total >= arr_len/2:\n",
    "                return res\n",
    "            else:\n",
    "                total += v\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSetSize(self, arr: List[int]) -> int:\n",
    "        map = {}\n",
    "        for i in arr:\n",
    "            if i not in map.keys():\n",
    "                map[i] = 1\n",
    "            else:\n",
    "                map[i]+=1\n",
    "        sort_map = dict(sorted(map.items(),key=lambda x:x[1], reverse=True))\n",
    "        halfsize = float(sum(sort_map.values())/2)\n",
    "        count = 0\n",
    "        rst = 0\n",
    "        for key,val in sort_map.items():\n",
    "            count +=val\n",
    "            rst += 1\n",
    "            if count>=halfsize:\n",
    "                return rst\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minSetSize(self, arr: List[int]) -> int:\r\n",
    "        dic = {}\r\n",
    "        n = 0\r\n",
    "        for v in arr:\r\n",
    "            if v in dic:\r\n",
    "                dic[v] += 1\r\n",
    "            else:\r\n",
    "                dic[v] = 1\r\n",
    "            n += 1\r\n",
    "        \r\n",
    "        lis = sorted(dic.items(), key = lambda x:(x[1], x[0]), reverse=True)\r\n",
    "        res = 0\r\n",
    "        total = 0\r\n",
    "        for i in range(len(lis)):\r\n",
    "            total += lis[i][1]\r\n",
    "            res += 1\r\n",
    "            if total >= (n + 1) // 2:\r\n",
    "                return(res)\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
